package main.leetcode.primary.from101to200;

/**
 * 154.寻找旋转排序数组中的最小值II
 *
 * <p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 *
 * <p>( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 *
 * <p>请找出其中最小的元素。
 *
 * <p>注意数组中可能存在重复的元素。
 *
 * <p>示例 1：
 *
 * <p>输入: [1,3,5] 输出: 1 示例 2：
 *
 * <p>输入: [2,2,2,0,1] 输出: 0 说明：
 *
 * <p>这道题是 寻找旋转排序数组中的最小值 的延伸题目。 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex154 {
    public static void main(String[] args) {
        System.out.println(new ex154().findMin(new int[] {2, 2, 2, 0, 1}));
        System.out.println(new ex154().findMin(new int[] {10, 1, 10, 10, 10}));
    }

    //    public int findMin(int[] nums) {
    //        int l = 0;
    //        int r = nums.length - 1;
    //        int mid;
    //        while (l < r) {
    //            if (nums[l] < nums[r]) {
    //                return nums[l];
    //            }
    //            mid = l + ((r - l) >> 1);
    //            if (nums[mid] < nums[r]) {
    //                r = mid;
    //            } else if (nums[mid] > nums[r]) {
    //                l = mid + 1;
    //            } else {
    //                //                l = nums[l] >= nums[mid] ? mid : l;
    //                --r;
    //            }
    //        }
    //        return nums[l];
    //    }

    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int mid;
        while (l < r) {
            if (nums[l] < nums[r]) {
                return nums[l];
            }
            mid = l + (r - l >> 1);
            if (nums[mid] < nums[r]) {
                r = mid;
            } else if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                --r;
            }
        }
        return nums[l];
    }
}
